Sharp Bounds on Davenport-Schinzel Sequences of Every Order

摘要

One of the longest-standing open problems in computational geometry is tobound the lower envelope of $n$ univariate functions, each pair of whichcrosses at most $s$ times, for some fixed $s$. This problem is known to beequivalent to bounding the length of an order-$s$ Davenport-Schinzel sequence,namely a sequence over an $n$-letter alphabet that avoids alternatingsubsequences of the form $a \cdots b \cdots a \cdots b \cdots$ with length$s+2$. These sequences were introduced by Davenport and Schinzel in 1965 tomodel a certain problem in differential equations and have since been appliedto bounding the running times of geometric algorithms, data structures, and thecombinatorial complexity of geometric arrangements. Let $\lambda_s(n)$ be the maximum length of an order-$s$ DS sequence over $n$letters. What is $\lambda_s$ asymptotically? This question has been answeredsatisfactorily (by Hart and Sharir, Agarwal, Sharir, and Shor, Klazar, andNivasch) when $s$ is even or $s\le 3$. However, since the work of Agarwal,Sharir, and Shor in the mid-1980s there has been a persistent gap in ourunderstanding of the odd orders. In this work we effectively close the problem by establishing sharp bounds onDavenport-Schinzel sequences of every order $s$. Our results reveal that,contrary to one's intuition, $\lambda_s(n)$ behaves essentially like$\lambda_{s-1}(n)$ when $s$ is odd. This refutes conjectures due to Alon et al.(2008) and Nivasch (2010).